package com.zz.study.sharding.algorithm.compress;

import com.zz.study.sharding.entity.DtFusdataFlink;
import com.zz.study.sharding.entity.DtFusdataFlinkSimple;
import com.zz.study.sharding.entity.GPSLocation;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class DPUtil {

    /**
     * 默认的点到轨迹线最大距离误差阈值（单位：米）
     */
    private static double defaultDMax = 30.0;

    /**
     * DP算法入口
     * 传入压缩前的轨迹点集合
     * 输出压缩后的结果轨迹点集合
     * @param originPoints 压缩前的轨迹点集合
     * @param dMax 点到轨迹线最大距离误差阈值
     * @return
     */
    public static List<DtFusdataFlink> dpAlgorithm(List<DtFusdataFlink> originPoints, Double dMax){
        List<DtFusdataFlink> resultPoints = new ArrayList<>();
        resultPoints.add(originPoints.get(0));//获取第一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(originPoints.size()-1));//获取最后一个原始经纬度点坐标并添加到过滤后的数组中
        //最大距离误差阈值
        if(dMax == null){
            dMax = defaultDMax;
        }
        int start = 0;
        int end = originPoints.size()-1;
        compression(originPoints,resultPoints,start,end,dMax);

        return resultPoints;
    }

    public static List<DtFusdataFlinkSimple> dpAlgorithmSimple(List<DtFusdataFlinkSimple> originPoints, Double dMax){
        List<DtFusdataFlinkSimple> resultPoints = new ArrayList<>();
        resultPoints.add(originPoints.get(0));//获取第一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(originPoints.size()-1));//获取最后一个原始经纬度点坐标并添加到过滤后的数组中
        //最大距离误差阈值
        if(dMax == null){
            dMax = defaultDMax;
        }
        int start = 0;
        int end = originPoints.size()-1;
        compressionSimple(originPoints,resultPoints,start,end,dMax);

        return resultPoints;
    }

    public static List<Map<String,Object>> dpAlgorithmMap(List<Map<String,Object>> originPoints, Double dMax){
        List<Map<String,Object>> resultPoints = new ArrayList<>();
        resultPoints.add(originPoints.get(0));//获取第一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(originPoints.size()-1));//获取最后一个原始经纬度点坐标并添加到过滤后的数组中
        //最大距离误差阈值
        if(dMax == null){
            dMax = defaultDMax;
        }
        int start = 0;
        int end = originPoints.size()-1;
        compressionMap(originPoints,resultPoints,start,end,dMax);

        return resultPoints;
    }

    /**
     * 函数功能：根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
     * @param originPoints：原始经纬度坐标点数组
     * @param resultPoints：保持过滤后的点坐标数组
     * @param start：起始下标
     * @param end：终点下标
     * @param dMax：预先指定好的最大距离误差 计算
     */
    public static void compression(List<DtFusdataFlink> originPoints, List<DtFusdataFlink> resultPoints,
                                     int start, int end, double dMax){
        if(start < end){//递归进行的条件
            double maxDist = 0;//最大距离
            int cur_pt = 0;//当前下标
            for(int i=start+1;i<end;i++){
                //当前点到对应线段的距离
                double curDist = distToSegment(originPoints.get(start),originPoints.get(end),originPoints.get(i));
                if(curDist > maxDist){
                    maxDist = curDist;
                    cur_pt = i;
                }//求出最大距离及最大距离对应点的下标
            }
            //若当前最大距离大于最大距离误差
            if(maxDist >= dMax){
                resultPoints.add(originPoints.get(cur_pt));//将当前点加入到过滤数组中
                //将原来的线段以当前点为中心拆成两段，分别进行递归处理
                compression(originPoints,resultPoints,start,cur_pt,dMax);
                compression(originPoints,resultPoints,cur_pt,end,dMax);
            }
        }
    }

    public static void compressionSimple(List<DtFusdataFlinkSimple> originPoints, List<DtFusdataFlinkSimple> resultPoints,
                                   int start, int end, double dMax){
        if(start < end){//递归进行的条件
            double maxDist = 0;//最大距离
            int cur_pt = 0;//当前下标
            for(int i=start+1;i<end;i++){
                //当前点到对应线段的距离
                double curDist = distToSegmentSimple(originPoints.get(start),originPoints.get(end),originPoints.get(i));
                if(curDist > maxDist){
                    maxDist = curDist;
                    cur_pt = i;
                }//求出最大距离及最大距离对应点的下标
            }
            //若当前最大距离大于最大距离误差
            if(maxDist >= dMax){
                resultPoints.add(originPoints.get(cur_pt));//将当前点加入到过滤数组中
                //将原来的线段以当前点为中心拆成两段，分别进行递归处理
                compressionSimple(originPoints,resultPoints,start,cur_pt,dMax);
                compressionSimple(originPoints,resultPoints,cur_pt,end,dMax);
            }
        }
    }


    public static void compressionMap(List<Map<String,Object>> originPoints, List<Map<String,Object>> resultPoints,
                                   int start, int end, double dMax){
        if(start < end){//递归进行的条件
            double maxDist = 0;//最大距离
            int cur_pt = 0;//当前下标
            for(int i=start+1;i<end;i++){
                //当前点到对应线段的距离
                double curDist = distToSegmentMap(originPoints.get(start),originPoints.get(end),originPoints.get(i));
                if(curDist > maxDist){
                    maxDist = curDist;
                    cur_pt = i;
                }//求出最大距离及最大距离对应点的下标
            }
            //若当前最大距离大于最大距离误差
            if(maxDist >= dMax){
                resultPoints.add(originPoints.get(cur_pt));//将当前点加入到过滤数组中
                //将原来的线段以当前点为中心拆成两段，分别进行递归处理
                compressionMap(originPoints,resultPoints,start,cur_pt,dMax);
                compressionMap(originPoints,resultPoints,cur_pt,end,dMax);
            }
        }
    }

    /**
     * 函数功能：使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
     * @param pA：起始点
     * @param pB：结束点
     * @param pX：第三个点
     * @return distance：点pX到pA和pB所在直线的距离
     */
    public static double distToSegment(DtFusdataFlink pA,DtFusdataFlink pB,DtFusdataFlink pX){
        double a = Math.abs(geoDist(pA, pB));
        double b = Math.abs(geoDist(pA, pX));
        double c = Math.abs(geoDist(pB, pX));
        double p = (a+b+c)/2.0;
        double s = Math.sqrt(Math.abs(p*(p-a)*(p-b)*(p-c)));
        double d = s*2.0/a;
        return d;
    }

    public static double distToSegmentSimple(DtFusdataFlinkSimple pA,DtFusdataFlinkSimple pB,DtFusdataFlinkSimple pX){
        double a = Math.abs(geoDistSimple(pA, pB));
        double b = Math.abs(geoDistSimple(pA, pX));
        double c = Math.abs(geoDistSimple(pB, pX));
        double p = (a+b+c)/2.0;
        double s = Math.sqrt(Math.abs(p*(p-a)*(p-b)*(p-c)));
        double d = s*2.0/a;
        return d;
    }

    public static double distToSegmentMap(Map<String,Object> pA,Map<String,Object> pB,Map<String,Object> pX){
        double a = Math.abs(geoDistMap(pA, pB));
        double b = Math.abs(geoDistMap(pA, pX));
        double c = Math.abs(geoDistMap(pB, pX));
        double p = (a+b+c)/2.0;
        double s = Math.sqrt(Math.abs(p*(p-a)*(p-b)*(p-c)));
        double d = s*2.0/a;
        return d;
    }

    /**
     * 函数功能：根据数学公式求两个经纬度点之间的距离
     * @param pA：起始点
     * @param pB：结束点
     * @return distance：距离
     */
    public static double geoDist(DtFusdataFlink pA,DtFusdataFlink pB){
        double radLat1 = Rad(pA.getLat());
        double radLat2 = Rad(pB.getLat());
        double delta_lon = Rad(pB.getLon() - pA.getLon());
        double top_1 = Math.cos(radLat2) * Math.sin(delta_lon);
        double top_2 = Math.cos(radLat1) * Math.sin(radLat2) - Math.sin(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
        double top = Math.sqrt(top_1 * top_1 + top_2 * top_2);
        double bottom = Math.sin(radLat1) * Math.sin(radLat2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
        double delta_sigma = Math.atan2(top, bottom);
        double distance = delta_sigma * 6378137.0;
        return distance;
    }

    public static double geoDistSimple(DtFusdataFlinkSimple pA,DtFusdataFlinkSimple pB){
        double radLat1 = Rad(pA.getLat());
        double radLat2 = Rad(pB.getLat());
        double delta_lon = Rad(pB.getLon() - pA.getLon());
        double top_1 = Math.cos(radLat2) * Math.sin(delta_lon);
        double top_2 = Math.cos(radLat1) * Math.sin(radLat2) - Math.sin(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
        double top = Math.sqrt(top_1 * top_1 + top_2 * top_2);
        double bottom = Math.sin(radLat1) * Math.sin(radLat2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
        double delta_sigma = Math.atan2(top, bottom);
        double distance = delta_sigma * 6378137.0;
        return distance;
    }

    public static double geoDistMap(Map<String,Object> pA,Map<String,Object> pB){
        double radLat1 = Rad( Double.valueOf(pA.get("Lat").toString()));
        double radLat2 = Rad(Double.valueOf(pB.get("Lat").toString()));
        double delta_lon = Rad(Double.valueOf(pB.get("Lon").toString()) - Double.valueOf(pA.get("Lon").toString()) );
        double top_1 = Math.cos(radLat2) * Math.sin(delta_lon);
        double top_2 = Math.cos(radLat1) * Math.sin(radLat2) - Math.sin(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
        double top = Math.sqrt(top_1 * top_1 + top_2 * top_2);
        double bottom = Math.sin(radLat1) * Math.sin(radLat2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
        double delta_sigma = Math.atan2(top, bottom);
        double distance = delta_sigma * 6378137.0;
        return distance;
    }

    /**
     * 函数功能：角度转弧度
     * @param d：角度
     * @return 返回的是弧度
     */
    public static double Rad(double d){
        return d * Math.PI / 180.0;
    }

}
